翻訳と辞書
Words near each other
・ "O" Is for Outlaw
・ "O"-Jung.Ban.Hap.
・ "Ode-to-Napoleon" hexachord
・ "Oh Yeah!" Live
・ "Our Contemporary" regional art exhibition (Leningrad, 1975)
・ "P" Is for Peril
・ "Pimpernel" Smith
・ "Polish death camp" controversy
・ "Pro knigi" ("About books")
・ "Prosopa" Greek Television Awards
・ "Pussy Cats" Starring the Walkmen
・ "Q" Is for Quarry
・ "R" Is for Ricochet
・ "R" The King (2016 film)
・ "Rags" Ragland
・ ! (album)
・ ! (disambiguation)
・ !!
・ !!!
・ !!! (album)
・ !!Destroy-Oh-Boy!!
・ !Action Pact!
・ !Arriba! La Pachanga
・ !Hero
・ !Hero (album)
・ !Kung language
・ !Oka Tokat
・ !PAUS3
・ !T.O.O.H.!
・ !Women Art Revolution


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

peripheral cycle : ウィキペディア英語版
peripheral cycle

In graph theory, a peripheral cycle (or peripheral circuit) in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part. Peripheral cycles (or, as they were initially called, peripheral polygons) were first studied by , and play important roles in the characterization of planar graphs and in generating the cycle spaces of nonplanar graphs.〔.〕
==Definitions==
A peripheral cycle C in a graph G can be defined formally in one of several equivalent ways:
*C is peripheral if it is a simple cycle in a connected graph with the property that, for every two edges e_1 and e_2 in G\setminus C, there exists a path in G that starts with e_1, ends with e_2, and has no interior vertices belonging to C.〔.〕
*C is peripheral if it is an induced cycle with the property that the subgraph G\setminus C formed by deleting the edges and vertices of C is connected.〔This is, essentially, the definition used by . However, Bruhn distinguishes the case that G has isolated vertices from disconnections caused by the removal of C.〕
*If C is any subgraph of G, a ''bridge''〔Not to be confused with bridge (graph theory), a different concept.〕 of C is a minimal subgraph B of G that is edge-disjoint from C and that has the property that all of its points of attachments (vertices adjacent to edges in both B and G\setminus B) belong to C.〔.〕 A simple cycle C is peripheral if it has exactly one bridge.〔This is the definition of peripheral cycles originally used by . use the same definition of a peripheral cycle, but with a different definition of a bridge that more closely resembles the induced-cycle definition for peripheral cycles.〕
The equivalence of these definitions is not hard to see: a connected subgraph of G\setminus C (together with the edges linking it to C), or a chord of a cycle that causes it to fail to be induced, must in either case be a bridge, and must also be an equivalence class of the binary relation on edges in which two edges are related if they are the ends of a path with no interior vertices in C.〔See e.g. Theorem 2.4 of , showing that the vertex sets of bridges are path-connected, see for a definition of bridges using chords and connected components, and also see for a definition of bridges using equivalence classes of the binary relation on edges.〕

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「peripheral cycle」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.